package 代码随想录_回溯.组合;

import java.util.*;

/**
 * @author zx
 * @create 2022-06-08 15:22
 */
public class 组合_77 {
    /**
     * 方法一：回溯(代码随想录,讲的真的不错)
     */
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> list = new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {
        dfs(n,k,1);
        return res;
    }
    private void dfs(int n,int k,int startIndex){
        //递归终止条件是：list的长度等于k
        if(list.size() == k){
            res.add(new ArrayList<>(list));
            return;
        }
        //遍历可能的搜索起点
        for(int i = startIndex;i <= n;i++){
            list.add(i);
            //下一轮搜索,设置的搜索起点要加1,因为组合数理不允许出现重复的元素
            dfs(n,k,i + 1);
            //回溯的操作,撤销本次处理的结果
            list.removeLast();
        }
    }
}
class way2{
    /**
     * 剪枝优化
     */
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> list = new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {
        dfs(n,k,1);
        return res;
    }
    private void dfs(int n,int k,int startIndex){
        //递归终止条件是：list的长度等于k
        if(list.size() == k){
            res.add(new ArrayList<>(list));
            return;
        }
        //遍历可能的搜索起点
        for (int i = startIndex;i <= n - (k - list.size()) + 1;i++) {//优化的地方
            list.add(i);
            //下一轮搜索,设置的搜索起点要加1,因为组合数理不允许出现重复的元素
            dfs(n,k,i + 1);
            //回溯的操作,撤销本次处理的结果
            list.removeLast();
        }
    }
}
